package NiuKe.List;

import java.util.*;

/**
 *本类用来做题：牛客网上的链表题。
 * 链接：https://www.nowcoder.com/exam/oj?page=1&tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
 */

class MySingleList {
//    创建一个链表
    static class ListNode {
        int val;
        ListNode next = null;
        public ListNode() {
        }
        public ListNode(int val) {
            this.val = val;
        }
    }
    public void createLink() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4; /* */
        head = listNode1;
    }
//    链表的头结点
    public ListNode head;
//    遍历整个链表
     public void display() {
         //如果说 把整个链表 遍历完成 那么 就需要 head == null
         // 如果说 你遍历到链表的尾巴  head.next == null
         ListNode cur = head;
         while (cur != null) {
             System.out.print(cur.val+" ");
             cur = cur.next;
         }
         System.out.println();
     }

//    链表头插法
     public void addFirst(int data){
         ListNode listNode = new ListNode(data);
         listNode.next = head;
         head = listNode;
     }
//     链表尾插法
     public void addLast(int data){
         ListNode listNode = new ListNode(data);
         if(head == null) {
             head = listNode;
             return;
         }
         ListNode cur = head;
         while (cur.next != null) {
             cur = cur.next;
         }
         cur.next = listNode;
     }
    /**
     * 1：反转链表
     *  给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
     *  解法：头插法
     */
     public ListNode ReverseList(ListNode head) {
         // 不加头结点的方式
         if (head == null || head.next == null ){
             return null;
         }
         ListNode cur=head.next;
         head.next=null;//假如头结点不置于空，那么遍历的时候会出错
         while (cur != null){
             ListNode curNext=cur.next;
             cur.next=head;
             head=cur;
             cur=curNext;
         }
         return head;
     }
    public ListNode ReverseList2(ListNode head) {
        // 加头结点的方式
        if (head == null || head.next == null ){
            return null;
        }
        ListNode pre=new ListNode(-1);
        pre.next = head;
        ListNode cur=head.next;
        head.next  =null;
        while (cur != null){
            head = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur =head;
        }
        head = pre.next;
        return head;
    }
    /**
     * 2：链表内指定区间反转
     *  将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
     *  解题思路：加一个前表头用来反转
     */
        public ListNode reverseBetween (ListNode head, int m, int n) {
            //加个表头
            ListNode res = new ListNode(-1);
            res.next = head;
            //前序节点
            ListNode pre = res;
            //当前节点
            ListNode cur = head;
            //找到m
            for(int i = 1; i < m; i++){
                pre = cur;
                cur = cur.next;
            }
            //从m反转到n
            for(int i = m; i < n; i++){
                ListNode temp = cur.next;
                cur.next = temp.next;
                temp.next = pre.next;
                pre.next = temp;
            }
            //返回去掉表头
            return res.next;
        }
    public ListNode reverseBetween2 (ListNode head, int m, int n) {
        //加个表头
        ListNode res = new ListNode(-1);
        res.next = head;
        //前序节点
        ListNode pre = res;
        //当前节点
        ListNode cur = head;
        //找到m
        for(int i = 1; i < m; i++){
            pre = cur;
            cur = cur.next;
        }
        //从m反转到n
        for(int i = m; i < n; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        //返回去掉表头
        return res.next;
    }
    /*将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
        如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
        你不能更改节点中的值，只能更改节点本身。*/
    public ListNode reverseKGroup(ListNode head, int k) {
        //先创建一个哑节点
        ListNode dummy = new ListNode(0);
        //让哑节点的指针指向链表的头
        dummy.next = head;
        //开始反转的前一个节点，比如反转的节点范围是[link1，link2],
        //那么pre就是link1的前一个节点
        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            //每k个反转，end是每k个链表的最后一个
            for (int i = 0; i < k && end != null; i++)
                end = end.next;
            //如果end是空，说明不够k个，就不需要反转了，直接退出循环。
            if (end == null)
                break;
            //反转开始的节点
            ListNode start = pre.next;
            //next是下一次反转的头结点，先把他记录下来
            ListNode next = end.next;
            //因为end是这k个链表的最后一个结点，把它和原来链表断开，
            //这k个节点我们可以把他们看做一个小的链表，然后反转这个
            //小链表
            end.next = null;
            //因为pre是反转链表的前一个节点，我们把小链表[start,end]
            //反转之后，让pre的指针指向这个反转的小链表
            pre.next = reverse(start);
            //注意经过上一步反转之后，start反转到链表的尾部了，就是已经
            //反转之后的尾结点了，让他之前下一次反转的头结点即可（上面分析
            //过，next就是下一次反转的头结点）
            start.next = next;
            //前面反转完了，要进入下一波了，pre和end都有重新赋值
            pre = start;
            end = start;
        }
        return dummy.next;
    }



    /**
     * 3：合并两个排序的链表
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 解法：增加一个表头节点，然后比较插入
     */
    public ListNode Merge(ListNode list1,ListNode list2) {
        //创建一个表头节点
        ListNode newHead=new ListNode(-1);
        ListNode tmp = null;
        //判断是否为空
        if (list1 ==null){
            return list2;
        }
        if (list2 == null){
            return  list1;
        }
        //依次插入
        while (list1 !=null && list2 !=null ) {
          if (list1.val <= list2.val){
              if (tmp == null){
                  tmp =list1;
                  newHead.next = list1;
              }else {
                  tmp.next=list1;
                  tmp=tmp.next;
              }
              list1=list1.next;
          }else{
              if (tmp == null) {
                  tmp = list2;
                  newHead.next = list2;
              }else {
                  tmp.next=list2;
                  tmp=tmp.next;
              }
              list2=list2.next;
          }
        }
        //判断是否有剩余
        if (list1 !=null){
            tmp.next=list1;
        }
        if (list2 !=null){
            tmp.next=list2;
        }
        //删除第一个头结点
        return newHead.next;
    }
    /**
     * 4：合并k个已排序的链表
     * 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点
     * 解题思路:与3相同。
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        ListNode list=null;
        for (int i = 0; i < lists.size(); i++) {
            ListNode getlist=lists.get(i);
            list=Merge(list,getlist);
        }
        return list;
    }

    /**
     * 5： 判断链表中是否有环
     *判断给定的链表中是否有环。如果有环则返回true，否则返回false。
     * 解法：快慢指针
     */
    public boolean hasCycle(ListNode head) {
        //判断异常情况
        if (head == null ){
            return false;
        }
        if( head.next == null){
            return false;
        }
        //初始化
        ListNode fast=head.next.next;
        ListNode slow=head.next;

        while( fast !=null && fast.next!=null){
            if (fast == slow || fast.next==slow){//奇数和偶数情况
                return true;
            }
            fast=fast.next.next;
            slow=slow.next;

        }
        return false;
    }

    /**
     *6:链表中环的入口结点
     * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
     * 解题思路:快慢指针,速度为2倍,路程相同的情况下,时间是一半
     */
    public static ListNode hasCycle1(ListNode head) {
        //先判断链表为空的情况
        if (head == null)
            return null;
        //快慢双指针
        ListNode fast = head;
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while (fast != null && fast.next != null) {
            //快指针移动两步
            fast = fast.next.next;
            //慢指针移动一步
            slow = slow.next;
            //相遇则有环，返回相遇的位置
            if (fast == slow)
                return slow;
        }
        //到末尾说明没有环，返回null
        return null;
    }
        public ListNode EntryNodeOfLoop(ListNode pHead) {
            ListNode slow = hasCycle1(pHead);
            //没有环
            if(slow == null)
                return null;
            //快指针回到表头
            ListNode fast = pHead;
            //再次相遇即是环入口
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
    }

    /**
     7: 链表中倒数最后k个结点
     输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
     如果该链表长度小于k，请返回一个长度为 0 的链表。
     解法：快慢指针:让先走k-1步,在遍历链表
     */
    public static ListNode FindKthToTail (ListNode pHead, int k) {
        //异常情况先排查
        if (pHead == null || k<=0){
            return null;
        }
        if (pHead.next == null){
            return pHead;
        }
        //运用快慢指针的原理，让slow走length-k-1步
        ListNode fast=pHead;
        ListNode solw=pHead;

        while(k-1>0){
            if (fast.next == null){
                return null;
            }
            fast=fast.next;
            k--;
        }
        while (fast.next != null){
            fast= fast.next;
            solw=solw.next;
        }
        return solw;
    }

    /**
     * 8:删除链表的倒数第n个节点
     * 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
     * 解法：先找到最后第n个结点的指针，然后删掉就行了
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        //新建一个表头
      ListNode newHead=new ListNode(-1);
      newHead.next=head;
      //cur放要删除的节点，pre是上一个结点
      ListNode cur=head;
      ListNode pre=newHead;
      ListNode fast=head;
      while (n-1 >0){
          fast=fast.next;
          n--;
      }
        while (fast.next != null){
            fast= fast.next;
            cur=cur.next;
            pre=pre.next;
        }
        //删除结点
        pre.next=cur.next;
        return newHead.next;
    }

    /**
     * 9:两个链表的第一个公共结点
     * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
     * 解法：让任何一个链表指针，遍历俩次这个链表就能解决速度不匹配的问题，拿值大小控制
     * 速度的话，会通过8/9的测试案例，如果这个结点值相同但是下一个值不同的话吗，拿值控制速度
     * 的方式就通过不了。
     *
     有公共节点的时候，N1和N2必会相遇，因为长度一样嘛，速度也一定，必会走到相同的地方的，所以当两者相等的时候，则会第一个公共的节点
     无公共节点的时候，此时N1和N2则都会走到终点，那么他们此时都是null，所以也算是相等了。
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       /* ListNode com;
        if (pHead1 == null ||pHead2== null){
            return null;
        }


        while (pHead1.next !=null && pHead2.next!=null){
            if (pHead1.val <pHead2.val){
                pHead1=pHead1.next;
            }
            else if (pHead1.val == pHead2.val){
                com=pHead1;
                return com;
            }else {
                pHead2= pHead2.next;
            }
        }*/
        ListNode l1=pHead1;
        ListNode l2=pHead2;
        while (l1 != l2){
            if (l1 == null ){
                l1=pHead2;
            }else {
                l1= l1.next;
            }
            if (l2 == null){
                l2=pHead1;
            }else {
                l2= l2.next;
            }
        }
        return l1;
    }

    /**
     * 10: 链表相加(二)
     *假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
     * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
     * 解题思路：先将两个链表反转,然后依次相加并创建一个临时变量用来存放进位
     */

    public ListNode addInList (ListNode head1, ListNode head2) {
        // 进行判空处理
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 反转h1链表
        head1 = reverse(head1);
        // 反转h2链表
        head2 = reverse(head2);
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head;
        // 记录进位的数值
        int tmp = 0;
        while(head1 != null || head2 != null){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            nHead.next = new ListNode(val%10);
            // 下一个节点
            nHead = nHead.next;

        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(tmp > 0){
            nHead.next = new ListNode(tmp);
        }
        // 重新反转回来返回
        return reverse(head.next);
    }

    // 反转链表
    ListNode reverse(ListNode head){
        if(head == null)
            return head;
        ListNode cur = head;
        ListNode node = null;
        while(cur != null){
            ListNode tail = cur.next;
            cur.next = node;
            node = cur;
            cur = tail;
        }
        return node;
    }

    /**
     * 11:单链表的排序
     * 给定一个节点数为n的无序单链表，对其按升序排序。
     * 解题思路：将链表中的数据先取出来，放到数组中，数组排好序在放回链表中
     */
    public ListNode sortInList2 (ListNode head) {
        if (head == null)return  null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode cur = head;
        while (cur != null){
            queue.offer(cur);
            cur = cur.next;
        }
        ListNode pre = new ListNode(-1);
        cur =pre;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            cur .next =queue.poll();
            cur =cur.next;
        }
        return pre.next;
    }
    public ListNode sortInList1 (ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return  head;
        }
        ListNode tmp=head;
        int n=0;
        while (tmp != null){
            n++;
            tmp=tmp.next;
        }
        int [] array=new int[n];
        tmp=head;
        for (int i = 0; i < n; i++) {
            array[i]=tmp.val;
            tmp= tmp.next;
        }
        Arrays.sort(array);
        tmp=head;
        for (int i = 0; i < n; i++) {
            tmp.val=array[i];
            tmp=tmp.next;
        }
        return  head;
    }
    /**
     * 官方思路
     *首先判断链表为空或者只有一个元素，直接就是有序的。
     * step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
     * step 3：从left位置将链表断开，刚好分成两个子问题开始递归。
     * step 4：将子问题得到的链表合并，参考合并两个有序链表。
     */
    //合并两段有序链表
    ListNode merge(ListNode pHead1, ListNode pHead2) {
        //一个已经为空了，直接返回另一个
        if(pHead1 == null)
            return pHead2;
        if(pHead2 == null)
            return pHead1;
        //加一个表头
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //两个链表都要不为空
        while(pHead1 != null && pHead2 != null){
            //取较小值的节点
            if(pHead1.val <= pHead2.val){
                cur.next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1.next;
            }else{
                cur.next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2.next;
            }
            //指针后移
            cur = cur.next;
        }
        //哪个链表还有剩，直接连在后面
        if(pHead1 != null)
            cur.next = pHead1;
        else
            cur.next = pHead2;
        //返回值去掉表头
        return head.next;
    }

    public ListNode sortInList (ListNode head) {
        //链表为空或者只有一个元素，直接就是有序的
        if(head == null || head.next == null)
            return head;
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //右边的指针到达末尾时，中间的指针指向该段链表的中间
        while(right != null && right.next != null){
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //左边指针指向左段的左右一个节点，从这里断开
        left.next = null;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid));
    }

    /**
     * 12:判断一个链表是否为回文结构
     *给定一个链表，请判断该链表是否为回文结构。
     * 回文是指该字符串正序逆序完全一致。
     * 解法：快慢指针找到中间结点，然后结点后面的利用头插法，从而实现回文串的访问
     */
    public boolean isPail (ListNode head) {
        ListNode p = head;
        int n = 0;
        //找到链表长度
        while(p != null){
            n++;
            p = p.next;
        }
        //中点
        n = n / 2;
        p = head;
        //遍历到中点位置
        while(n > 0){
            p = p.next;
            n--;
        }
        //中点处反转
        p = reverse(p);
        ListNode q = head;
        while(p != null){
            //比较判断节点值是否相等
            if(p.val != q.val)
                return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }

    /**
     * 13: 链表的奇偶重排
     *给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
     * 注意是节点的编号而非节点的数值。
     * 解题思路：创建俩个额外的链表，分别用来存放奇数偶数，遍历完成后将俩个链表合并到一起
     */

    public ListNode oddEvenList (ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return  head;
        }
        ListNode p=head;
        int n=1;//用来判断是奇数偶数
       ListNode Js=new ListNode(-1);//奇数链表
       ListNode Os=new ListNode(-1);//偶数链表
        ListNode cur = Js;
        ListNode cur1 = Os;
       while (p!=null){
           if (n%2!=0){//如果是奇数的话，用尾插法插到奇数链表后
               ListNode listNode = new ListNode(p.val);
               cur.next = listNode;
               cur=listNode;
           } else{//如果是偶数的话，用尾插法插到偶数链表后
               ListNode listNode = new ListNode(p.val);
               cur1.next = listNode;
               cur1=listNode;
           }
           p=p.next;
           n++;
       }
       p=Js;
       //将俩个链表合并
       while (p.next!=null){
           p=p.next;
       }
       p.next=Os.next;
       return Js.next;
    }
    //官话解法，真聪明,就是一次性跳俩个指针,因为他是下标为奇数偶数而不是值为奇数偶数,所以能用这个方法，
    public ListNode oddEvenList1 (ListNode head) {
        //如果链表为空，不用重排
        if(head == null)
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next;
        //odd开头指向第一个节点
        ListNode odd = head;
        //指向even开头
        ListNode evenhead = even;
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next;
            //odd进入后一个奇数位
            odd = odd.next;
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next;
            //even进入后一个偶数位
            even = even.next;
        }
        //even整体接在odd后面
        odd.next = evenhead;
        return head;
    }

    /**
     * 14:删除有序链表中重复的元素
     * 删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null){
            return null;
        }
        if (head.next == null){
            return  head;
        }
        ListNode pre=new ListNode(-1);//创建一个头结点
        pre.next=head;
        ListNode p=head;
        while (p != null){

            if (pre.val == p.val){
                pre.next=p.next;//如果相等就删掉这个节点
                p=pre.next;

            }else{
                pre=pre.next;
                p=p.next;
            }
        }

        return head;
    }
    /**
     * 15: 删除有序链表中重复的元素-II
     * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
     * 解题思路：创建一个新的头结点以防止删除第一个头结点,将相同的都跳过,链表只指向没有出现过的节点
     */
    public ListNode deleteDuplicates2 (ListNode head) {
        //空链表
        if(head == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }
}

public class Test {
    public static void main(String[] args) {
        //14测试
        MySingleList mySingleList=new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.display();
     mySingleList.ReverseList2(mySingleList.head);
        mySingleList.display();
    }
    public static void main2(String[] args) {
        //13测试
        MySingleList mySingleList=new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(4);
        mySingleList.addLast(6);
        mySingleList.addLast(3);
        mySingleList.addLast(7);
        mySingleList.display();
        mySingleList.head=mySingleList.oddEvenList(mySingleList.head);
        mySingleList.display();

    }

    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        MySingleList mySingleList2 = new MySingleList();
//        mySingleList.createLink();
//        mySingleList2.createLink();
//        mySingleList.display();
//        mySingleList.addLast(5);
//        mySingleList.display();
       // mySingleList.reverseBetween(mySingleList.head,2,4);
      //  mySingleList.display();
       // mySingleList.removeNthFromEnd(mySingleList.head,2);
        //mySingleList.display();
        //mySingleList.removeNthFromEnd(mySingleList.head,1);
        //mySingleList.display();
       ;
        mySingleList.addLast(9);
        mySingleList.addLast(3);
        mySingleList.addLast(7);
        mySingleList2.addLast(6);
        mySingleList2.addLast(3);

        mySingleList.head=mySingleList.addInList(mySingleList.head,mySingleList2.head);
        mySingleList.display();

    }

}

